package com.ujs.listnode.code.cycleLinkedList;

import com.ujs.listnode.code.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangshihao
 * @create 2023-10-11 21:13
 * <p>
 * 142. 环形链表 II
 * https://leetcode.cn/problems/linked-list-cycle-ii/
 * https://www.programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E6%80%9D%E8%B7%AF
 */
public class CycleLinkedList {
    public static void main(String[] args) {
        // ListNode head = new ListNode(3);
        // ListNode node1 = new ListNode(2);
        // ListNode node2 = new ListNode(0);
        // ListNode node3 = new ListNode(-4);
        // head.next = node1;
        // node1.next = node2;
        // node2.next = node3;
        // node3.next = node1;
        ListNode head = new ListNode(1);
        ListNode listNode = detectCycle2(head);
        System.out.println(listNode);
    }

    public static ListNode detectCycle(ListNode head) {
        List<ListNode> listNodes = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            for (ListNode listNode : listNodes) {
                if (cur == listNode) {
                    return cur;
                }
            }
            listNodes.add(cur);
            cur = cur.next;
        }
        return null;
    }

    public static ListNode detectCycle2(ListNode head) {
        // 定义fast和slow节点，fast每次移动两格，slow移动一格。这样fast最终都会和slow相遇
        ListNode fast = head;
        ListNode slow = head;
        // 分别记录fast和slow节点在相遇时一共走过的节点数量。
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode index1 = slow; // 从相遇节点出发
                ListNode index2 = head; // 从头节点出发
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        // System.out.println("相遇的节点：" + slow.val + "slow走过的数量" + slowCount);
        // System.out.println("相遇的节点：" + fast.val + "fast走过的数量" + fastCount);
        /* 通过数学计算，得出相交的节点
        假设，相交之前的节点数量为Z，环中slow走的数量为X，剩下的数量为Y
        slow走的节点数为：Z+X；fast走的节点数为：Z+n(X+Y)+X  n表示圈数
        fast走过的节点数为slow走过的节点数的两倍：2(z+x) = z+n(x+y)+x
        得到 2z+2x = z+nx+ny+x   =>  x+z=n(x+y)  要求的是z。所以 z=n(x+y)-x  =>
        z=(n-1)x+y。

        公式说明了：
        当n=1时，意味着fast指针在环形里面走了一圈就遇到了slow指针。此时公式为 z=y
        这就意味着，从头节点出发一个指针，从 相遇节点 出发一个指针，这两个指针每次只走一个节点，
        那么当这两个指针相遇的时候，就是 环形入口的节点

        那么 n如果大于1是什么情况呢，就是fast指针在环形转n圈之后才遇到 slow指针。
        其实这种情况和n为1的时候 效果是一样的，一样可以通过这个方法找到 环形的入口节点，
        只不过，index1 指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。
        */
        return null;
    }


    /**
     * 定义快慢两个指针，快指针每次走两格，慢指针每次走一格。
     * 当快指针和慢指针相遇时，结束循环。
     * 在定义一个index指针从头结点出发，慢指针接着走，当index和慢指针相遇时，即为相遇的点。
     *
     * @param head
     * @return
     */
    public static ListNode detectCycle3(ListNode head) {
        // 定义fast和slow节点，fast每次移动两格，slow移动一格。这样fast最终都会和slow相遇
        ListNode fast = head;
        ListNode slow = head;
        do {
            fast = fast.next.next;
            slow = slow.next;
        } while (fast != slow);

        slow = head; // 从头节点出发
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}
